A conventional error correcting coding technique is Reed-Solomon codes. Reed-Solomon Codes are described in the non-patent literature 1, for example.
An encoding process for an error correcting code is a process of determining an output vector b by multiplying an input vector a in the form of a plaintext by a linear transformation (i.e., a matrix) A, which can be expressed by the formula (1). More specifically, the i-th row of the matrix A indicates coefficients by which the elements of the input vector a are multiplied in order to produce the i-th element bi of the output vector b.b=Aa  (1)
A decoding process for the error correcting code can also be regarded as a linear transformation. Provided that A′ and b′ are a matrix and a vector obtained by extracting only the rows corresponding to k elements of the matrix A and the vector b used for the decoding, respectively, the decoding process can be expressed by the formula (2).b′=A′a  (2)
Thus, if the matrix A has an inverse matrix, the vector a can be decoded according to the formula (3).a=A′−1b′  (3)In encoding for the error correcting code, it is assumed that the input vector a is a k-th order vector expressed by the formula (4), where k denotes an integer equal to or greater than 2.
                    a        =                  (                                                                      a                  0                                                                                    ⋮                                                                                      a                                      k                    -                    1                                                                                )                                    (        4        )            
It is assumed that the output vector b is an n-th order vector expressed by the formula (5), where n denotes an integer equal to or greater than 2, and n≥2k−1.
                    b        =                  (                                                                      b                  0                                                                                    ⋮                                                                                      b                                      n                    -                    1                                                                                )                                    (        5        )            
The matrix A is a matrix formed by vertically connecting a k-by-k unit matrix and an m-by-k Vandennonde matrix, where m=n−k. The Vandermonde matrix is a matrix having a special configuration in which elements of rows or columns are the terms of a geometric progression sequentially arranged.
                              A          ij                =                  {                                                    1                                                                                  if                    ⁢                                                                                  ⁢                    i                                    =                  j                                                                                    0                                                                                  if                    ⁢                                                                                  ⁢                    i                                    ≠                                      j                    ⁢                                                                                  ⁢                    and                    ⁢                                                                                  ⁢                    i                                    <                  k                                                                                                      x                                                            (                                              i                        -                        k                                            )                                        ⁢                    j                                                                                                                    if                    ⁢                                                                                  ⁢                    i                                    ≥                  k                                                                                        (        6        )            wherei∈{0, . . . , n−1}, j∈{0, . . . , k−1}
In short, the matrix A is an n-by-k matrix expressed by the formula (7).
                                          (                                                            1                                                  0                                                  0                                                  …                                                  0                                                                              0                                                  1                                                  0                                                  …                                                  0                                                                              0                                                  0                                                  1                                                  …                                                  0                                                                              ⋮                                                  ⋮                                                  ⋮                                                  ⋱                                                  ⋮                                                                              0                                                  0                                                  0                                                  …                                                  1                                                                              1                                                  1                                                  1                                                  …                                                  1                                                                              1                                                  x                                                                      x                    2                                                                    …                                                                      x                                          k                      -                      1                                                                                                                    1                                                                      x                    2                                                                                        x                    4                                                                    …                                                                      x                                          2                      ⁢                                              (                                                  k                          -                          1                                                )                                                                                                                                          ⋮                                                  ⋮                                                  ⋮                                                  ⋱                                                  ⋮                                                                              1                                                                      x                                          m                      -                      1                                                                                                            x                                          2                      ⁢                                              (                                                  m                          -                          1                                                )                                                                                                              …                                                                      x                                                                  (                                                  m                          -                          1                                                )                                            ⁢                                              (                                                  k                          -                          1                                                )                                                                                                                  )                                ︸                          k              ⁢                                                          ⁢              columns                                      ⁢                                            }                                                      k                ⁢                                                                  ⁢                rows                                                                        }                                                      m                ⁢                                                                  ⁢                rows                                                                        (        7        )            
Since the matrix A is a identity matrix up to the k-th row thereof, the first to k-th elements b0, . . . , bk−1 of the output vector b agree with the elements a0, . . . , ak−1 of the input vector a. The elements of the output vector b that agree with the corresponding elements of the input vector a are referred to as a “data share”, and the other elements are referred to as a “parity share”.